#include "../bulk_storage/bulk_storage.h"

#ifndef _M_TREE_H
#define _M_TREE_H


/** 
    \defgroup mTree
    @{

    mTree provides indexing for any data using a user-defined metric
    function.  It can be backed by any properly implemented store
    object.  (Although constructors only exist for cacheStore and
    memStore.) 
    
    The branch factor is currently globally decided at compile time.

    The metric function, d(), must obey the following rules, for all a, b, and c:

    d(a,b) = d(b,a)

    d(a,b) > 0

    d(a,c) <= d(a,b) + d(b,c)

    To allow for floating point error, the above inequalities have
    been relaxed somewhat.  All runtime comparisons made by mTree must
    be within 0.01% of being true. 

    @see mTree_new_memory, mTree_open_cached, mTree_size, mTree_close, mTree_insert, mTree_rangeQuery, mTree_print, mTree_printStats and mTree_verify

    @todo Change mTree to use a #define to decide on the acceptable
    floating point error in the distance function.

    \ingroup Indices
**/

struct mTree {
  struct store * oStore;
  struct store * nStore;
  int rootNode;
  double (*distance)(const void *, const void *);
};

/**
   The branching factor for mTree.  Currently, this is global to prevent run-time lookups.
   10-15 seem to be good values.
*/
#define MTREE_BFACTOR 15


/**
   Create a new mTree backed by two memStore stores.
   
   @see store_new_memory
*/
struct mTree * mTree_new_memory(size_t objectSize,
				double (*distance)(const void *, const void*));
/**
   Create a new mTree with nodes backed by a cacheStore.  The objects
   are kept in the store passed in by the user.  This allows more than
   one mTree to be built on top of a single physical copy of the data.

   @see store_new_cached
*/
struct mTree * mTree_open_cached(struct store * oStore, const char * nFile, 
				 const char * nFat, size_t cacheSize, 
				 double (*distance)(const void *, const void*));


/**
   This function is a bit slower than necessary, since it traverses
   the tree.  It was implemented as a way to provide sanity checking
   to tree builders.  If you need to use it heavily, mTree_insert
   could increment a counter in mTree, and you could simply return the
   value of the counter here.

   @return the number of objects in this tree.
*/
off_t mTree_size(struct mTree * tree);


/** 
    Close the mTree, and release any resources that it is occupying.
*/
void mTree_close(struct mTree * tree);
/** 
    Insert a node.

    @param object The index of the object to be inserted.  The object
    must already be present in the oStore store passed into the
    constructor.

*/
void mTree_insert(struct mTree * tree, /*void * object*/ off_t storeNumber);

/**
    Perform a range query.

    @param queryObject This is just an ordinary object, like the ones
    you would pass into insert.

    @param queryDist This is an integer 'radius', in the same units as
    the distance funciton specifies.

    @param processHit This is a pointer to a void function that takes
    two arguments.  The first argument is a pointer to an object that
    matched the query.  The second argument is the pointer provided in
    the state parameter of the call to mTree_rangeQuery

    @param state A pointer to whatever state information is used by
    processHit.  This is only used by the processHit function that is
    supplied by the user, and may be null if no state information is
    required.

*/
void mTree_rangeQuery(struct mTree * tree, void * queryObject, int queryDist, 
		      void (*processHit)(void * matchingObject, void * state), 
		      void * state);

/**
   Dump the tree to standard out.  For a more concise listing, try
   running 'grep -v NULL' on the output.
*/
void mTree_print(struct mTree * tree);
void mTree_printStats(struct mTree * tree);

void mTree_verify(struct mTree * tree);
/**
   @}
*/

/**
   xyzi objects can be inserted into mTree's for testing purposes.
*/
/*struct xyzi {
  int x;
  int y;
  int z;
  int i;  // I is the external identifier of this object
  };*/

//double xyzi_dist(struct xyzi* a, struct xyzi* b);
/**
   @param null Ignored.  Present to conform to the format expected by mTree_rangeQuery()
*/
//void xyzi_print(struct xyzi* a, void * null);




#endif // _M_TREE_H
